package leetcode; /**
 * description:
 * author:张腾
 * date:2021-07-11
 */

/**
 * 对链表进行插入排序。
 *
 * 插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
 * 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
 */
public class leetcode147 {
    public ListNode insertionSortList(ListNode head) {
        if (head==null) return head;
        ListNode dum = new ListNode(0);
        dum.next = head;
        ListNode lastSorted = head, cur = head.next;

        while (cur!=null){
            if (cur.val>=lastSorted.val) lastSorted = lastSorted.next;
            else{
                ListNode pre = dum;
                while (pre.next.val<= cur.val) pre = pre.next;

                lastSorted.next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
            }
            cur = lastSorted.next;
        }
        return dum.next;
    }
}
